#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/1 10:52
# ===========================================
#       题目名称： 84. 柱状图中最大的矩形
#       题目地址： https://leetcode.cn/problems/largest-rectangle-in-histogram/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================
import time


class Solution:

    def largestRectangleArea(self, heights):
        """
            以空间换时间
        """
        max_area = 0
        heights = [0] + heights + [0]
        stack = []
        for i in range(len(heights)):
            # print(stack)
            while stack and heights[stack[-1]] > heights[i]:
                top = stack.pop()
                max_area = max(max_area, heights[top] * (i - stack[-1] - 1))
            stack.append(i)
        return max_area

    def largestRectangleArea11(self, heights):
        """
            以空间换时间
        """
        max_area = 0
        all_heights = []  # 枚举处所以可能性
        if len(set(heights)) == 1:
            max_area = heights[0] * len(heights)
        else:
            while heights:
                top = heights.pop()
                all_heights.append([top, ])
                cur_heights = [top, ]
                temp_heights = heights.copy()
                while temp_heights:
                    temp_top = temp_heights.pop()
                    cur_heights.insert(0, temp_top)
                    all_heights.append(cur_heights.copy())
            for all_height in all_heights:
                max_area = max(max_area, min(all_height) * len(all_height))
        return max_area

    def largestRectangleArea10(self, heights):
        """
            以空间换时间 效率不行
            [2,1,5,6,2,3]
            [2]
            [1]
            [2,1]
            [5]
            [1,5]
            [2,1,5]
        """
        max_area = 0  # 找到最大宽度
        while heights:
            top = heights.pop()
            max_area = max(top, max_area)  # 初始化一下
            temp_height = heights.copy()
            count = 1
            while temp_height:
                count += 1
                temp_top = temp_height.pop()
                top = min(top, temp_top)
                max_area = max(max_area, count * top)
        return max_area

    def largestRectangleArea9(self, heights):
        """
            获取最小值 效率有问题
        """
        max_area = 0  # 找到最大宽度
        temp_heights = []
        for height in heights:
            if height == 0:
                temp_heights = []
                continue
            temp_heights.append(height)
            if max_area >= height * len(temp_heights):
                continue
            if len(set(temp_heights)) == 1:
                max_area = max(max_area, temp_heights[0] * len(temp_heights))
                continue
            cur_index = len(temp_heights) - 1
            while cur_index > -1:
                max_area = max(max_area, min(temp_heights[cur_index:]) * (len(temp_heights) - cur_index))
                cur_index -= 1
        return max_area

    def largestRectangleArea8(self, heights):
        """
            获取最小值 时间超限
            2,1,5,6,2,3
            2
            1
            1,2
            5
            5,1
            5,1,2
            6
            6,5
            6,5,1
            6,5,1,2
            2
            2,6
            2,6,5
            2,6,5,1
            2,6,5,1,2
            3
            3,2
            3,2,6
            3,2,6,5
            3,2,6,5,1
            3,2,6,5,1,2
        """
        max_area = 0  # 找到最大宽度
        temp_heights = []
        for index, height in enumerate(heights):
            temp_heights.append(height)
            cur_index = index
            while cur_index > -1:
                max_area = max(max_area, min(temp_heights[cur_index:]) * (index - cur_index + 1))
                cur_index -= 1
        return max_area

    def largestRectangleArea7(self, heights):
        """
            效率不够
            找到比自己当前这个值大的 比自己小的停止
        """
        max_width = 0  # 找到最大宽度
        count = 0  # 计数器
        for index, height in enumerate(heights):
            if height == 0 or index == len(heights) - 1:
                max_width = max(max_width, count)
                count = 0
            else:
                count += 1
        max_area = 0  # 最大面积
        if heights.count(heights[0]) == len(heights):
            return heights[0] * len(heights)
        for index, height in enumerate(heights):
            if height == 0 or len(heights) * height < max_width:
                continue
            count = 0  # 有几个符合规范
            # 左边
            for l_index in reversed(range(0, index)):  # 从大到小 0, index
                if heights[l_index] < height or heights[l_index] == 0:
                    break
                count += 1
            # 右边
            for r_index in range(index, len(heights)):
                if heights[r_index] < height or heights[r_index] == 0:
                    break
                count += 1
            # 求最大值
            max_area = max(max_area, height * count)
        return max_area

    def largestRectangleArea6(self, heights):
        stack = []
        max_area = 0
        i = 0

        while i < len(heights):
            if not stack or heights[i] >= heights[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                top = stack.pop()
                area = heights[top] * (i if not stack else i - stack[-1] - 1)
                max_area = max(max_area, area)

        while stack:
            top = stack.pop()
            area = heights[top] * (i if not stack else i - stack[-1] - 1)
            max_area = max(max_area, area)

        return max_area

    def get_max_val(self, heights, max_val):
        left, right = 0, len(heights) - 1
        while left < right:
            # print(left , right)
            min_val = min(heights[left: right + 1]) * (right - left + 1)
            max_val = max(max_val, min_val)

        return max_val

    def largestRectangleArea5(self, heights):
        """
            逻辑有问题
        """
        # 1. 先求一个最大值
        max_val = max(heights)  # 获取当个最大值
        # 2. 在判断是否为1 为0
        cp_heights = heights.copy()  # 复制一份
        cp_heights.sort()  # 排序
        distinct_element = list(set(cp_heights))  # 去重的元素
        if len(set(distinct_element)) == 1:  # 判断是否所有的元素都是相同的
            if distinct_element[0] == 0:  # 如果为0 返回0
                return max_val
            return len(heights) * distinct_element[0]  # 宽度 * 高度
        # 判断是否有0 如果有0 就进行切割
        if heights.count(0) > 0:
            # indices_of_zero = [i for i, x in enumerate(heights) if x == 0]  # 获取每个0的下标
            # start_index = 0
            # for index in indices_of_zero:
            #     max_val = self.get_max_val(heights[start_index: index], max_val)
            #     start_index = index + 1
            start_index = 0
            for index, height in enumerate(heights):
                if height == 0 or index == len(heights) - 1:
                    max_val = self.get_max_val(heights[start_index: index + 1], max_val)
                    start_index = index + 1
        else:
            max_val = self.get_max_val(heights, max_val)
        return max_val

    def largestRectangleArea4(self, heights):
        """
            超出时间限制
        """
        max_val = max(heights)  # 找出最大值
        cp_heights = heights.copy()  # 复制一份
        cp_heights.sort()  # 排序
        distinct_element = list(set(cp_heights))  # 去重的元素
        if len(set(distinct_element)) == 1:  # 判断是否所有的元素都是相同的
            if distinct_element[0] == 0:  # 如果为0 返回0
                return max_val
            return len(heights) * distinct_element[0]  # 宽度 * 高度
        # 定义左右指针向中间靠拢
        left, right = 0, len(heights) - 1
        while left <= right:
            temp_height = heights[left: right + 1]
            temp_height.sort()
            min_val = temp_height[0]
            if min_val != 0:
                max_val = max(max_val, min_val * (right - left + 1))
            if right - 1 == left:
                if left + 1 > len(heights) - 1:
                    break
                else:
                    left += 1
                    right = len(heights) - 1
            else:
                right -= 1
        return max_val

    def largestRectangleArea3(self, heights):
        """
            排序 去重 根据 每个元素 找到 >= 的 进行求最大值
            解答错误
        """
        max_val = max(heights)  # 找出最大值
        cp_heights = heights.copy()  # 复制一份
        cp_heights.sort()  # 排序
        distinct_element = list(set(cp_heights))  # 去重的元素
        if len(set(distinct_element)) == 1:  # 判断是否所有的元素都是相同的
            if distinct_element[0] == 0:  # 如果为0 返回0
                return max_val
            return len(heights) * distinct_element[0]  # 宽度 * 高度
        if distinct_element[0] == 0:
            del distinct_element[0]
        for element in distinct_element:  # 根据每个元素去找
            print(element, max_val)
            if element * len(heights) < max_val:  # 如果当前元素 比当前元素*最大宽度比最大值小 就直接跳过
                continue
            # 定义左右指针 左指针找当前这个元素 右指针 找>=的元素
            left, right = 0, 1
            while left < right < len(heights):
                while left < len(heights) - 2 and heights[left] != element:
                    left += 1
                right = left + 1
                while right < len(heights) - 1 and heights[right] < element:
                    right += 1
                # 找到left right
                # 求最大值
                cur_height = heights[left: right + 1]
                cur_height.sort()
                min_val = cur_height[0]
                max_val = max(max_val, min_val * (right - left + 1))
                # 替换
                left += 1
                right = left + 1
        return max_val

    def largestRectangleArea2(self, heights):
        """
            超出时间限制
        """
        # 找出单个最大值
        max_val = max(heights)
        if len(heights) == 1:
            return max_val
        if len(set(heights)) == 1:
            if heights[0] == 0:
                return max_val
        return len(heights) * heights[0]

        # 定义左右指针
        left, right = 0, 1  # left , right += 1 0 跳过
        while left < right < len(heights):
            print(left, right)
            if heights[left] == 0:
                left += 1
                right = left + 1
                continue
            if right + 1 < len(heights) and heights[right] == 0:
                left += 1
                right = left + 1
                continue
            # 做业务逻辑
            if left == right:
                max_val = max(max_val, heights[left])
            else:
                cur_height = heights[left: right + 1]
                cur_height.sort()
                min_val = cur_height[0]
                max_val = max(max_val, min_val * (right - left + 1))
            # 变更 left right
            if right + 1 > len(heights) - 1:
                if left + 1 > len(heights) - 2:
                    break
                else:
                    left += 1
                    right = left + 1
            else:
                right += 1
        return max_val

    def largestRectangleArea2(self, heights):
        """
            解答有误
        """
        temp_height = heights.copy()
        temp_height.sort(reverse=True)
        max_val = temp_height[0]
        if len(temp_height) == 1:
            return max_val
        while temp_height:
            cur_temp_height = temp_height.pop()
            left, right = 0, len(heights) - 1  # 定义左右坐标     左向右靠拢 求最
            while left < right and heights[left] < cur_temp_height:
                left += 1
            while right >= 0 and heights[right] < cur_temp_height:
                right -= 1
            # 找到左右位置
            if left == right:
                max_val = max(max_val, heights[left])
            else:
                cur_height = heights[left: right + 1]
                cur_height.sort()
                min_val = cur_height[0]
                max_val = max(max_val, min_val * (right - left + 1))
        return max_val


if __name__ == '__main__':
    s = Solution()
    # 4
    print("heights = [2,4] =>", s.largestRectangleArea(heights=[2, 4]))
    # 10
    print("heights = [2,1,5,6,2,3] =>", s.largestRectangleArea(heights=[2, 1, 5, 6, 2, 3]))
    # 1
    print("heights = [1] =>", s.largestRectangleArea(heights=[1]))
    # 4
    print("heights = [2,3] =>", s.largestRectangleArea(heights=[2, 3]))
    # 9
    print("heights = [0,9] =>", s.largestRectangleArea(heights=[0, 9]))
    # 2
    print("heights = [2,0,2] =>", s.largestRectangleArea(heights=[2, 0, 2]))
    # 14
    print("heights = [6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3] =>", s.largestRectangleArea(heights=[6, 4, 2, 0, 3, 2, 0, 3, 1, 4, 5, 3, 2, 7, 5, 3, 0, 1, 2, 1, 3, 4, 6, 8, 1, 3]))
    # 6
    print("heights = [4,2,0,3,2,5] =>", s.largestRectangleArea(heights=[4, 2, 0, 3, 2, 5]))
    # 12
    print("heights = [5,5,1,7,1,1,5,2,7,6] =>", s.largestRectangleArea(heights=[5, 5, 1, 7, 1, 1, 5, 2, 7, 6]))
    # 12
    print(s.largestRectangleArea(heights=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ]))
